/**
 * https://leetcode-cn.com/problems/maximum-subarray/
 * 最大子序和
 * @param nums 
 */
// 动态规划优化
function maxSubArray(nums: number[]): number {
    // 长度为一, 直接返回
    if (nums.length === 1) return nums[0]

    const len = nums.length;

    let sum = nums[0],
        max = sum;

    for (let i = 1; i < len; i++) {
        // 更新sum
        sum = Math.max(sum + nums[i], nums[i])
        
        // 更新max
        max = Math.max(max, sum)
    }
    return max;
};

// 动态规划
function maxSubArray2(nums: number[]): number {
    // [-2,1,-3,4,-1,2,1,-5,4]
    // 长度为一, 直接返回
    if (nums.length === 1) return nums[0]

    const len = nums.length;
    // dp[i] 表示以i结尾的元素的最长子序和
    // dp[i] = max{dp[i - 1], nums[i]} 前一项的最大子序和和当前元素比大小
    const dp: number[] = new Array(len + 1);
    let max = dp[0] = Number.MIN_SAFE_INTEGER
    for (let i = 1; i <= len; i++) {
        // 获取当前的最大和
        dp[i] = Math.max(dp[i - 1] + nums[i - 1], nums[i - 1])
        max = Math.max(max, dp[i])
    }
    return max;
};





//! 不通过
const maxSubArray1 = (nums: number[]): number => {
    const len = nums.length;
    // 只有一项
    if (len === 1) return nums[0]

    let ans = nums[0];

    // 遍历数组
    for (let i = 1; i < len; i++) {
        const curr = nums[i]
        // 当前值小于等于0
        if (curr < 0) {
            // 当前和大于0, 计算当前值后面总和能否抵消掉这个负数 || 能否有值大于当前的总和
            let total = 0,
                hasBigger = false
            for (let j = i; j < len; j++) {
                // 后面又某项大于当前的和, 直接从哪项开始
                total += nums[j]
                if (nums[j] > ans) {
                    i = j;
                    ans = nums[j]
                    hasBigger = true
                    break;
                }
            }
            if (hasBigger) {
                // 有更大的
                continue
            } else {
                // 总和能抵消
                // 没有更大的
                if (total + curr >= 0) {
                    ans += curr
                } else {
                    // 总和不能抵消, 结束
                    break;
                }
            }
        } else {
            // 原来的和小于0, 和重新开始计算
            if (ans <= 0) ans = curr
            else ans += curr
        }
    }

    return ans
};

// console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
// console.log(maxSubArray([-2, 3, -2, -1, 4]))
// console.log(maxSubArray([-9, -8, -1, -3, 0]))
// console.log(maxSubArray([-2, -1]))